Salenko lập kỉ lục World Cup - ghi 5 bàn thắng trong một trận đấu - cho đội tuyển Nga trong trận gặp Cameroon ngày 28 tháng 6 năm 1994. Tại World Cup 1994 anh ghi được 6 bàn thắng, giành được danh hiệu Vua phá lưới cùng với Hristo Stoichkov, một thành tích đáng nhớ mặc dù Nga bị loại ngay từ vòng 1, và Stoichkov thi đấu cùng Bulgaria nhiều hơn Salenko 4 trận. Thành tích này của Salenko tương tự thành tích anh lập được tại giải Vô địch thế giới lứa tuổi dưới 20 năm 1989 tại Ả Rập Xê Út: Vua phá lưới với 5 bàn thắng.

Salenko chỉ thi đấu tổng cộng 9 trận đấu quốc tế, trong đó có 1 trận cho Ukraina, mặc dù tiền đạo tài năng này có một sự nghiệp ở câu lạc bộ khá thành công, khoác áo các câu lạc bộ Zenit Leningrad, Dynamo Kiev, Logroñés, Cordoba CF, Valencia, Rangers và Istanbulspor từ năm 1986 đến năm 2000.

Thực ra Salenko sớm phải từ giã sự nghiệp thi đấu quốc tế nói riêng và thi đấu nói chung do gặp phải những chấn thương kể từ mùa bóng 1996-97. Anh trở lại với bóng đá vào mùa bóng 2000-01 khi ký hợp đồng với câu lạc bộ Ba Lan Pogoń Szczecin. Tuy nhiên chỉ sau 1 trận đấu Salenko đã không đủ điều kiện về thể lực và cân nặng, đành chia tay câu lạc bộ và giải nghệ.